package class_0822Graph;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

public class Coding_Dijkstral {
    /**
     * 迪利斯特拉的经典算法
     * 改进方法:使用优先队列.
     * distanceMap:
     * key---结点
     * Integer---distance key到head的最短路径
     * ----------------
     * selectedNodes:
     * key 存放已经走过的结点
     * @param head:起点
     * @return 图中所有结点到head的最短距离.---一个哈希表
     */
    public static HashMap<Node, Integer> dijkstral(Node head){

        HashMap<Node, Integer> distanceMap = new HashMap<>();
        distanceMap.put(head, 0);
        HashSet<Node>  selectedNodes = new HashSet<>();
        Node minNode = getMinDistanceAndUnselectedNode(distanceMap,selectedNodes);
        while(minNode != null){
            //之前的距离
            int distance = distanceMap.get(minNode);
            //遍历当前顶点关联的所有边
            for(Edge edge : minNode.edges){
                Node toNode = edge.to;
                if (!distanceMap.containsKey(toNode)) {
                    //这是新增距离
                    distanceMap.put(toNode, distance + edge.weight);
                }
                else {
                    //比较是否需要更新
                    if(distance+edge.weight<distanceMap.get(toNode)) {
                        distanceMap.put(edge.to, distance + edge.weight);
                    }
                }
            }
            selectedNodes.add(minNode);
            minNode = getMinDistanceAndUnselectedNode(distanceMap,selectedNodes);
        }
        return distanceMap;
    }
    public static Node getMinDistanceAndUnselectedNode(HashMap<Node,Integer> distanceMap, HashSet<Node> selectNodes){
        Node minNode = null;
        int minDistance = Integer.MAX_VALUE;
        for(Map.Entry<Node, Integer> entry:distanceMap.entrySet()){
            int distance = entry.getValue();
            Node node = entry.getKey();
            if(!selectNodes.contains(node) && distance<minDistance) {
                minNode = node;
                minDistance = distance;
            }
        }
        return minNode;
    }
}
